package kyssion.leetcode.num51_100;

import kyssion.leetcode.util.ListNode;

public class code82_删除列表中的重复元素2 {

    public static void main(String[] args) {
        ListNode node = ListNode.createListNode(new int[]{
                0, 0, 1, 1, 2, 2, 3, 3, 3, 4, 4, 5, 5, 6
        });
        node = new code82_删除列表中的重复元素2().deleteDuplicates2(node);
        ListNode.showListNode(node);
    }

    public ListNode deleteDuplicates(ListNode head) {
        ListNode start = new ListNode(-1);
        start.next = head;
        head = start;
        ListNode before = start;
        ListNode item = start.next;
        boolean needDelte = false;
        while (item != null) {
            if (before != start && before.val == item.val) {
                needDelte = true;
            } else {
                if (needDelte) {
                    head.next = item;
                    needDelte = false;
                } else if (before != start) {
                    head = head.next;
                }
            }
            before = before.next;
            item = item.next;
        }
        if (needDelte) {
            head.next = item;
        }
        return start.next;
    }

    /**
     * 方法 2 递归写法 超级简单
     *
     * @param head
     * @return
     */
    public ListNode deleteDuplicates2(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode node = head;
        boolean flag = false;
        while (head.next != null && head.val == head.next.val) {
            head = head.next;
            flag = true;
        }
        if (!flag) {
            node.next = deleteDuplicates2(head.next);
            return node;
        }
        return deleteDuplicates2(head.next);
    }
}
